Modern computers in operation are busy. Keyboards are stroked, screens flicker, and millions of bytes are transformed each second. With the recent prevalence and popularity of portable computers, there is a real need for computers that consume less power. With portable computers, such as laptops, power consumption is a major concern for the system designer. It is well-known that dead batteries are the major cause of failure of portable computers and dead batteries invariably lead to user dissatisfaction. In fact, most battery operated computer systems will inevitably cease to function after hours of operation, unless the batteries are replaced or recharged.
Conventional low-power computer systems generally run at lower clock rates or slower speeds, which often results in reduced reliability and performance. One technique that is sometimes used to improve the performance of a conventional computer system is to allow certain portions or subsystems of the computer to operate autonomously by providing the subsystem with programmable control in the form of, for example, a microprocessor and associated support structures such as memory, and bus interfaces. With an autonomous subsystem, a large number of the subsystem operations can be handled in parallel by the microprocessor, making the host system available for other functions.
An example of an autonomously operating subsystem may be found in input/output (I/O) controllers. I/O controllers generally control the data transfer between the various peripheral devices and the computer. For example, a typical I/O controller, such as a video display terminal (VDT) controller, in response to keystrokes (input data) typed by the user will cause the computer to transfer information (output data) to a display screen. Similarly, a disk controller, in response to user initiated events from the host computer will transfer files between the host CPU and a disk drive. The complex device control functions that are involved in data transfers are generally processed autonomously by the I/O subsystem.
One characteristic of I/O controllers is that they operate sporadically, generally only in response to externally generated events. A VDT I/O controller, as an obvious example, even when used by a fast typist, only needs to be active a couple of times a second, with frequent long waits between key strokes while the user studies and edits displayed information. Similarly, a disk I/O controller may be requested to transfer a file for display or editing purposes from time to time. The augmented file is written back to the disk minutes, or perhaps hours later. In typical conventional computers, the subsystems spend a disproportionate amount of time, while surreptitiously consuming power, busily polling peripheral devices to determine if an attention requiring event has occurred.
State machines have previously been used for achieving fault tolerance, and for implementing decentralized control in distributed systems. State machines, because of their empirically provable predictable behavior, have also been used to implement complex language compilers, report generators, bus protocols, and network processors. However, state machine notation, unlike a traditional flowchart, is extremely difficult for most users to conceptualize and therefore is normally not used in general data processing applications.
Simplistically articulated, a state machine typically converts a time series of event stimuli or input data through some function into a time series of responses or output data. More formally, a state machine (SM) is a mathematical model to describe the structure and operation of a machine comprising:
a set of states, S={S.sub.0, . . . ,S.sub.n } PA1 a set of events, E={e.sub.0, . . . ,e.sub.m } PA1 a next state function, F: S.times.E=s PA1 an output function, Q: S.times.E=a or r, and PA1 a starting state, S.sub.0.
In operation, the machine starts in an initial state so, and a sequence of time driven events selected from the set E is applied to the machine. The next state s of the machine, after application of an event, is determined by the next state function F. The output resulting from a state transition is determined from the function Q. If the output is a, the event has been accepted and processed, if the output is r, the event has been rejected or not processed.
Since the machine can assume any one of its next states only in response to a predeterminable number of events, the maximum number of states that the machine can assume is easily computable, hence state machines of this type are sometimes known as finite state machines. Because of the predictable nature of state machines, computer systems implemented by using this technique are generally more reliable than systems implemented by using more conventional techniques, such as traditional decision based flowcharts or data based structured charts.
Any state of the machine is the memory of sufficient history of the machine to determine future behavior. In terms of the state machine, this means sufficient information to determine both an output and a next state if the present inputs are known. State machines are generally pictorially represented by a directed graph where each node corresponds to a state of the machine, and each directed arrow indicates a possible transition from one state to another, in response to a particular event. In state diagrams, the first or top node, as depicted further herein, will be assigned to the initial state (so) of a machine.
Now, during operation of a conventional state machine, the stimulating events are generally presented in an orderly manner. For example, a state machine for a language compiler or report generator may read a source file in order to determine the sequence of stimulating events, such as the characters or words that constitute the source text. Similarly, a state machine for a network or bus protocol processor usually continuously scans the input lines to determine if new events in the form of communication data packets are present. In other words, these types of data driven state machines constantly monitor the sources of input events. Such data driven state machines are relatively responsive and efficient as long as the events necessary to transition or operate the machine appear as a constant stream. However, if the time interval between events is extended or sporadic, valuable computer resources, such as power, are wasted while the state machine is busily looking for a nonexistent next event to process.
Improvements have been made to such traditional data driven state machines by providing them with a clocking mechanism. Instead of constantly monitoring the sources of input events, the state machine only examines the source of events on a periodic basis as determined by the clocking mechanism. Although these types of clock driven state machines consume less power by polling the input source less frequently, they do have a disadvantage in being less responsive. Any events that are generated between clock pulses are not recognized and processed until the expiration of a predetermined time interval. Even if the clock rate is adjusted in accordance with the rate of event presentation, optimal responsiveness is difficult to achieve.